package ai.zixing.mashibing.advance_class.first.class01;

import java.util.LinkedList;

/**
 * 力扣真题: https://leetcode.cn/problems/sliding-window-maximum/
 */
public class Code01_SlidingWindowMaxArray {
    public static int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length < k) {
            return null;
        }
        // 其中存放的是位置，头代表（大 -> 小） 尾
        LinkedList<Integer> qmax = new LinkedList<>();
        // 窗口可能的状态集合
        int[] res = new int[nums.length - k + 1];
        int index = 0;
        // R : R
        for (int R = 0; R < nums.length; R++) {

            ///===============进窗口
            // R -> 可以妨碍比他大的数后，后者为空
            while (!qmax.isEmpty() && nums[qmax.peekLast()] <= nums[R]) {
                // 如果小于当前，则弹出，弹出到空或者大于等于当前
                qmax.pollLast();
            }
            qmax.addLast(R);
            ///===============进窗口

            // 如果窗口没到达到 k, 不弹出数字，达到 k 则弹出
            if (qmax.peekFirst() == R - k) {
                qmax.pollFirst();
            }
            ///以上将窗口的更新做完了

            /// 收集答案
            if (R >= k - 1) {
                res[index++] = nums[qmax.peekFirst()];
            }
        }
        return res;
    }
}
